package com.practice.misc;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SmileHouse {
	public static void main(String[] args) {
		new SmileHouse().run();
	}
	
	private int N, M;
	private int[][] c;
	private int INF = -3000001;
	
	private void run() {
		try {
//			BufferedReader f = new BufferedReader(new FileReader("src/test/resources/smilehouse6.in"));
			BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
			int[] a = read(f, 2);
			N = a[0];
			M = a[1];
			c = new int[N][N];
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {
					c[i][j] = INF;
				}
			}
			for (int i=0; i<M; i++) {
				a = read(f, 4);
				c[a[0]-1][a[1]-1] = a[2];
				c[a[1]-1][a[0]-1] = a[3];
			}
			
//			int low = 1;
//			int high = N; 
//			if (!search(N)) {
//				System.out.println(0);
//				return;
//			}
//			
//			while (low < high-1) {
//				int mid = (low + high + 1) / 2;
//				if (search(mid)) {
//					high = mid;
//				}
//				else {
//					low = mid;
//				}
//			}
//			
//			System.out.println((low+high+1)/2);
			
			for (int i=1; i<=N; i++) {
				if (search(i)) {
					System.out.println(i);
					return;
				}
			}
			System.out.println(0);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	// exists positive cycle in n-node?
	private boolean search(int n) {
		int[][] m = clone(c);
		int[][] v = clone(c);
		n = n - 1;
		while (n > 0) {
			if ((n&1) > 0) m = multiply(m, v);
			v = multiply(v, v);
			n >>= 1;
		}
		
		for (int i=0; i<N; i++) {
			if (m[i][i] > 0) return true;
		}
		return false;
	}
	
	private int[][] clone(int[][] m) {
		int[][] t = new int[N][N];
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				t[i][j] = m[i][j];
			}
		}
		return t;
	}
	
	private int[][] multiply(int[][] m1, int[][] m2) {
		int[][] m = new int[N][N];
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				int cost = INF;
				for (int k=0; k<N; k++) {
					if (i!=k && j!=k && m1[i][k]!=INF && m2[k][j]!=INF) {
						cost = Math.max(cost, m1[i][k] + m2[k][j]);
					}
				}
				m[i][j] = cost;
			}
		}
		
		return m;
	}
	
	public int[] read(BufferedReader f, int N) throws IOException {
		String[] t = f.readLine().split(" ");
		int[] a = new int[N];
		for (int i=0; i<N; i++) {
			a[i] = Integer.parseInt(t[i]);
		}
		return a;
	}
}
